<html><head><meta charset="utf-8"><title>06 LinkedList 源码解析   -慕课专栏</title>
			<meta http-equiv="X-UA-Compatible" content="IE=edge, chrome=1">
			<meta name="renderer" content="webkit">
			<meta property="qc:admins" content="77103107776157736375">
			<meta property="wb:webmaster" content="c4f857219bfae3cb">
			<meta http-equiv="Access-Control-Allow-Origin" content="*">
			<meta http-equiv="Cache-Control" content="no-transform ">
			<meta http-equiv="Cache-Control" content="no-siteapp">
			<link rel="apple-touch-icon" sizes="76x76" href="https://www.imooc.com/static/img/common/touch-icon-ipad.png">
			<link rel="apple-touch-icon" sizes="120x120" href="https://www.imooc.com/static/img/common/touch-icon-iphone-retina.png">
			<link rel="apple-touch-icon" sizes="152x152" href="https://www.imooc.com/static/img/common/touch-icon-ipad-retina.png">
			<link href="https://moco.imooc.com/captcha/style/captcha.min.css" rel="stylesheet">
			<link rel="stylesheet" href="https://www.imooc.com/static/moco/v1.0/dist/css/moco.min.css?t=201907021539" type="text/css">
			<link rel="stylesheet" href="https://www.imooc.com/static/lib/swiper/swiper-3.4.2.min.css?t=201907021539">
			<link rel="stylesheet" href="https://static.mukewang.com/static/css/??base.css,common/common-less.css?t=2.5,column/zhuanlanChapter-less.css?t=2.5,course/inc/course_tipoff-less.css?t=2.5?v=201907051055" type="text/css">
			<link charset="utf-8" rel="stylesheet" href="https://www.imooc.com/static/lib/ueditor/themes/imooc/css/ueditor.css?v=201907021539"><link rel="stylesheet" href="https://www.imooc.com/static/lib/baiduShare/api/css/share_style0_16.css?v=6aba13f0.css"></head>
			<body><div id="main">


<div class="main-con hide-menu">
    <!-- 左侧菜单 & 索引 -->
    
    <div class="right-content" style="padding-left: 0px;">
        <div class="container clearfix" id="top" style="width: 1134px; display: block;">
            
            
            <div class="center_con js-center_con l" style="width: 1134px;">
                <div class="article-con">
                                            <!-- 买过的阅读 -->
                        

                    
                    <div class="art-title" style="margin-top: 0px;">
                        06 LinkedList 源码解析   
                    </div>
                    <div class="art-info clearfix">
                        
                        <span class="l">
                            更新时间：2019-09-05 17:37:46
                        </span>
                    </div>
                    <div class="art-top">
                                                <img src="https://img4.mukewang.com/5d63560c0001044d06400359.jpg" alt="">
                                                                        <div class="famous-word-box">
                            <img src="https://www.imooc.com/static/img/column/bg-l.png" alt="" class="bg1 bg">
                            <img src="https://www.imooc.com/static/img/column/bg-r.png" alt="" class="bg2 bg">
                            <div class="famous-word">智慧，不是死的默念，而是生的沉思。<p class="author">——斯宾诺莎</p></div>
                        </div>
                                            </div>
                    <div class="art-content js-lookimg">
                        <div id="article_content">
                            <div class="cl-preview-section"><h2 id="引导语" style="font-size: 30px;">引导语</h2>
</div><div class="cl-preview-section"><p style="font-size: 20px; line-height: 38px;">LinkedList 适用于集合元素先入先出和先入后出的场景，在队列源码中被频繁使用，面试也经常问到，本小节让我们通过源码来加深对 LinkedList 的了解。</p>
</div><div class="cl-preview-section"><h2 id="整体架构" style="font-size: 30px;">1 整体架构</h2>
</div><div class="cl-preview-section"><p style="font-size: 20px; line-height: 38px;">LinkedList 底层数据结构是一个双向链表，整体结构如下图所示：<br>
<img class="" src="https://img.mukewang.com/5d5fc67a0001f59212400288.png" data-original="//img.mukewang.com/5d5fc67a0001f59212400288.png" alt="图片描述">上图代表了一个双向链表结构，链表中的每个节点都可以向前或者向后追溯，我们有几个概念如下：</p>
</div><div class="cl-preview-section"><ul>
<li style="font-size: 20px; line-height: 38px;">链表每个节点我们叫做 Node，Node 有 prev 属性，代表前一个节点的位置，next 属性，代表后一个节点的位置；</li>
<li style="font-size: 20px; line-height: 38px;">first 是双向链表的头节点，它的前一个节点是 null。</li>
<li style="font-size: 20px; line-height: 38px;">last 是双向链表的尾节点，它的后一个节点是 null；</li>
<li style="font-size: 20px; line-height: 38px;">当链表中没有数据时，first 和 last 是同一个节点，前后指向都是 null；</li>
<li style="font-size: 20px; line-height: 38px;">因为是个双向链表，只要机器内存足够强大，是没有大小限制的。</li>
</ul>
</div><div class="cl-preview-section"><p style="font-size: 20px; line-height: 38px;">链表中的元素叫做 Node，我们看下 Node 的组成部分：</p>
</div><div class="cl-preview-section"><pre class="  language-java"><code class="prism  language-java"><span class="token keyword">private</span> <span class="token keyword">static</span> <span class="token keyword">class</span> <span class="token class-name">Node</span><span class="token operator">&lt;</span>E<span class="token operator">&gt;</span> <span class="token punctuation">{</span>
    E item<span class="token punctuation">;</span><span class="token comment">// 节点值</span>
    Node<span class="token operator">&lt;</span>E<span class="token operator">&gt;</span> next<span class="token punctuation">;</span> <span class="token comment">// 指向的下一个节点</span>
    Node<span class="token operator">&lt;</span>E<span class="token operator">&gt;</span> prev<span class="token punctuation">;</span> <span class="token comment">// 指向的前一个节点</span>

    <span class="token comment">// 初始化参数顺序分别是：前一个节点、本身节点值、后一个节点</span>
    <span class="token function">Node</span><span class="token punctuation">(</span>Node<span class="token operator">&lt;</span>E<span class="token operator">&gt;</span> prev<span class="token punctuation">,</span> E element<span class="token punctuation">,</span> Node<span class="token operator">&lt;</span>E<span class="token operator">&gt;</span> next<span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span>item <span class="token operator">=</span> element<span class="token punctuation">;</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span>next <span class="token operator">=</span> next<span class="token punctuation">;</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span>prev <span class="token operator">=</span> prev<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span>
</code></pre>
</div><div class="cl-preview-section"><h2 id="源码解析" style="font-size: 30px;">2 源码解析</h2>
</div><div class="cl-preview-section"><h3 id="追加（新增）">2.1 追加（新增）</h3>
</div><div class="cl-preview-section"><p style="font-size: 20px; line-height: 38px;">追加节点时，我们可以选择追加到链表头部，还是追加到链表尾部，add 方法默认是从尾部开始追加，addFirst 方法是从头部开始追加，我们分别来看下两种不同的追加方式：</p>
</div><div class="cl-preview-section"><p style="font-size: 20px; line-height: 38px;"><strong>从尾部追加（add）</strong></p>
</div><div class="cl-preview-section"><pre class="  language-java"><code class="prism  language-java"><span class="token comment">// 从尾部开始追加节点</span>
<span class="token keyword">void</span> <span class="token function">linkLast</span><span class="token punctuation">(</span>E e<span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token comment">// 把尾节点数据暂存</span>
    <span class="token keyword">final</span> Node<span class="token operator">&lt;</span>E<span class="token operator">&gt;</span> l <span class="token operator">=</span> last<span class="token punctuation">;</span>
    <span class="token comment">// 新建新的节点，初始化入参含义：</span>
    <span class="token comment">// l 是新节点的前一个节点，当前值是尾节点值</span>
    <span class="token comment">// e 表示当前新增节点，当前新增节点后一个节点是 null</span>
    <span class="token keyword">final</span> Node<span class="token operator">&lt;</span>E<span class="token operator">&gt;</span> newNode <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">Node</span><span class="token operator">&lt;</span><span class="token operator">&gt;</span><span class="token punctuation">(</span>l<span class="token punctuation">,</span> e<span class="token punctuation">,</span> null<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token comment">// 新建节点追加到尾部</span>
    last <span class="token operator">=</span> newNode<span class="token punctuation">;</span>
    <span class="token comment">//如果链表为空（l 是尾节点，尾节点为空，链表即空），头部和尾部是同一个节点，都是新建的节点</span>
    <span class="token keyword">if</span> <span class="token punctuation">(</span>l <span class="token operator">==</span> null<span class="token punctuation">)</span>
        first <span class="token operator">=</span> newNode<span class="token punctuation">;</span><span class="token operator">!</span><span class="token punctuation">[</span>图片描述<span class="token punctuation">]</span><span class="token punctuation">(</span><span class="token comment">//img.mukewang.com/5d5fc69600013e4803600240.gif)</span>
    <span class="token comment">//否则把前尾节点的下一个节点，指向当前尾节点。</span>
    <span class="token keyword">else</span>
        l<span class="token punctuation">.</span>next <span class="token operator">=</span> newNode<span class="token punctuation">;</span>
    <span class="token comment">//大小和版本更改</span>
    size<span class="token operator">++</span><span class="token punctuation">;</span>
    modCount<span class="token operator">++</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
</code></pre>
</div><div class="cl-preview-section"><p style="font-size: 20px; line-height: 38px;">从源码上来看，尾部追加节点比较简单，只需要简单地把指向位置修改下即可，我们做个动图来描述下整个过程：<br>
<img class="" src="https://img.mukewang.com/5d5fc6a300013e4803600240.gif" data-original="//img.mukewang.com/5d5fc6a300013e4803600240.gif" alt="图片描述"><br>
<strong>从头部追加（addFirst）</strong></p>
</div><div class="cl-preview-section"><pre class="  language-java"><code class="prism  language-java"><span class="token comment">// 从头部追加</span>
<span class="token keyword">private</span> <span class="token keyword">void</span> <span class="token function">linkFirst</span><span class="token punctuation">(</span>E e<span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token comment">// 头节点赋值给临时变量</span>
    <span class="token keyword">final</span> Node<span class="token operator">&lt;</span>E<span class="token operator">&gt;</span> f <span class="token operator">=</span> first<span class="token punctuation">;</span>
    <span class="token comment">// 新建节点，前一个节点指向null，e 是新建节点，f 是新建节点的下一个节点，目前值是头节点的值</span>
    <span class="token keyword">final</span> Node<span class="token operator">&lt;</span>E<span class="token operator">&gt;</span> newNode <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">Node</span><span class="token operator">&lt;</span><span class="token operator">&gt;</span><span class="token punctuation">(</span>null<span class="token punctuation">,</span> e<span class="token punctuation">,</span> f<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token comment">// 新建节点成为头节点</span>
    first <span class="token operator">=</span> newNode<span class="token punctuation">;</span>
    <span class="token comment">// 头节点为空，就是链表为空，头尾节点是一个节点</span>
    <span class="token keyword">if</span> <span class="token punctuation">(</span>f <span class="token operator">==</span> null<span class="token punctuation">)</span>
        last <span class="token operator">=</span> newNode<span class="token punctuation">;</span>
    <span class="token comment">//上一个头节点的前一个节点指向当前节点</span>
    <span class="token keyword">else</span>
        f<span class="token punctuation">.</span>prev <span class="token operator">=</span> newNode<span class="token punctuation">;</span>
    size<span class="token operator">++</span><span class="token punctuation">;</span>
    modCount<span class="token operator">++</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
</code></pre>
</div><div class="cl-preview-section"><p style="font-size: 20px; line-height: 38px;">头部追加节点和尾部追加节点非常类似，只是前者是移动头节点的 prev 指向，后者是移动尾节点的 next 指向。</p>
</div><div class="cl-preview-section"><h3 id="节点删除">2.2 节点删除</h3>
</div><div class="cl-preview-section"><p style="font-size: 20px; line-height: 38px;">节点删除的方式和追加类似，我们可以选择从头部删除，也可以选择从尾部删除，删除操作会把节点的值，前后指向节点都置为 null，帮助 GC 进行回收。</p>
</div><div class="cl-preview-section"><p style="font-size: 20px; line-height: 38px;"><strong>从头部删除</strong></p>
</div><div class="cl-preview-section"><pre class="  language-java"><code class="prism  language-java"><span class="token comment">//从头删除节点 f 是链表头节点</span>
<span class="token keyword">private</span> E <span class="token function">unlinkFirst</span><span class="token punctuation">(</span>Node<span class="token operator">&lt;</span>E<span class="token operator">&gt;</span> f<span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token comment">// 拿出头节点的值，作为方法的返回值</span>
    <span class="token keyword">final</span> E element <span class="token operator">=</span> f<span class="token punctuation">.</span>item<span class="token punctuation">;</span>
    <span class="token comment">// 拿出头节点的下一个节点</span>
    <span class="token keyword">final</span> Node<span class="token operator">&lt;</span>E<span class="token operator">&gt;</span> next <span class="token operator">=</span> f<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
    <span class="token comment">//帮助 GC 回收头节点</span>
    f<span class="token punctuation">.</span>item <span class="token operator">=</span> null<span class="token punctuation">;</span>
    f<span class="token punctuation">.</span>next <span class="token operator">=</span> null<span class="token punctuation">;</span>
    <span class="token comment">// 头节点的下一个节点成为头节点</span>
    first <span class="token operator">=</span> next<span class="token punctuation">;</span>
    <span class="token comment">//如果 next 为空，表明链表为空</span>
    <span class="token keyword">if</span> <span class="token punctuation">(</span>next <span class="token operator">==</span> null<span class="token punctuation">)</span>
        last <span class="token operator">=</span> null<span class="token punctuation">;</span>
    <span class="token comment">//链表不为空，头节点的前一个节点指向 null</span>
    <span class="token keyword">else</span>
        next<span class="token punctuation">.</span>prev <span class="token operator">=</span> null<span class="token punctuation">;</span>
    <span class="token comment">//修改链表大小和版本</span>
    size<span class="token operator">--</span><span class="token punctuation">;</span>
    modCount<span class="token operator">++</span><span class="token punctuation">;</span>
    <span class="token keyword">return</span> element<span class="token punctuation">;</span>
<span class="token punctuation">}</span>
</code></pre>
</div><div class="cl-preview-section"><p style="font-size: 20px; line-height: 38px;">从尾部删除节点代码也是类似的，就不贴了。</p>
</div><div class="cl-preview-section"><p style="font-size: 20px; line-height: 38px;"><strong>从源码中我们可以了解到，链表结构的节点新增、删除都非常简单，仅仅把前后节点的指向修改下就好了，所以 LinkedList 新增和删除速度很快。</strong></p>
</div><div class="cl-preview-section"><h3 id="节点查询">2.3 节点查询</h3>
</div><div class="cl-preview-section"><p style="font-size: 20px; line-height: 38px;">链表查询某一个节点是比较慢的，需要挨个循环查找才行，我们看看 LinkedList 的源码是如何寻找节点的：</p>
</div><div class="cl-preview-section"><pre class="  language-java"><code class="prism  language-java"><span class="token comment">// 根据链表索引位置查询节点</span>
Node<span class="token operator">&lt;</span>E<span class="token operator">&gt;</span> <span class="token function">node</span><span class="token punctuation">(</span><span class="token keyword">int</span> index<span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token comment">// 如果 index 处于队列的前半部分，从头开始找，size &gt;&gt; 1 是 size 除以 2 的意思。</span>
    <span class="token keyword">if</span> <span class="token punctuation">(</span>index <span class="token operator">&lt;</span> <span class="token punctuation">(</span>size <span class="token operator">&gt;&gt;</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        Node<span class="token operator">&lt;</span>E<span class="token operator">&gt;</span> x <span class="token operator">=</span> first<span class="token punctuation">;</span>
        <span class="token comment">// 直到 for 循环到 index 的前一个 node 停止</span>
        <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> index<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span>
            x <span class="token operator">=</span> x<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
        <span class="token keyword">return</span> x<span class="token punctuation">;</span>
    <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token punctuation">{</span><span class="token comment">// 如果 index 处于队列的后半部分，从尾开始找</span>
        Node<span class="token operator">&lt;</span>E<span class="token operator">&gt;</span> x <span class="token operator">=</span> last<span class="token punctuation">;</span>
        <span class="token comment">// 直到 for 循环到 index 的后一个 node 停止</span>
        <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> size <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">&gt;</span> index<span class="token punctuation">;</span> i<span class="token operator">--</span><span class="token punctuation">)</span>
            x <span class="token operator">=</span> x<span class="token punctuation">.</span>prev<span class="token punctuation">;</span>
        <span class="token keyword">return</span> x<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span>
</code></pre>
</div><div class="cl-preview-section"><p style="font-size: 20px; line-height: 38px;">从源码中我们可以发现，LinkedList 并没有采用从头循环到尾的做法，而是采取了简单二分法，首先看看 index 是在链表的前半部分，还是后半部分。如果是前半部分，就从头开始寻找，反之亦然。通过这种方式，使循环的次数至少降低了一半，提高了查找的性能，这种思想值得我们借鉴。</p>
</div><div class="cl-preview-section"><h3 id="方法对比">2.4 方法对比</h3>
</div><div class="cl-preview-section"><p style="font-size: 20px; line-height: 38px;">LinkedList 实现了 Queue 接口，在新增、删除、查询等方面增加了很多新的方法，这些方法在平时特别容易混淆，在链表为空的情况下，返回值也不太一样，我们列一个表格，方便大家记录：</p>
</div><div class="cl-preview-section"><div class="table-wrapper"><table>
<thead>
<tr>
<th>方法含义</th>
<th>返回异常</th>
<th>返回特殊值</th>
<th>底层实现</th>
</tr>
</thead>
<tbody>
<tr>
<td>新增</td>
<td> add(e)</td>
<td>offer(e)</td>
<td> 底层实现相同</td>
</tr>
<tr>
<td>删除</td>
<td> remove()</td>
<td>poll(e)</td>
<td> 链表为空时，remove 会抛出异常，poll 返回 null。</td>
</tr>
<tr>
<td>查找</td>
<td> element(e)</td>
<td>peek(e)</td>
<td> 链表为空时，element 会抛出异常，peek 返回 null。</td>
</tr>
</tbody>
</table>
</div></div><div class="cl-preview-section"><p style="font-size: 20px; line-height: 38px;">LinkedList 也实现了 Deque 接口，对新增、删除和查找都提供从头开始，还是从尾开始两种方向的方法，比如 remove 方法，Deque 提供了 removeFirst 和 removeLast 两种方向的使用方式，但当链表为空时的表现都和 remove 方法一样，都会抛出异常。</p>
</div><div class="cl-preview-section"><h3 id="迭代器">2.5 迭代器</h3>
</div><div class="cl-preview-section"><p style="font-size: 20px; line-height: 38px;">因为 LinkedList 要实现双向的迭代访问，所以我们使用 Iterator 接口肯定不行了，因为 Iterator 只支持从头到尾的访问。Java 新增了一个迭代接口，叫做：ListIterator，这个接口提供了向前和向后的迭代方法，如下所示：</p>
</div><div class="cl-preview-section"><div class="table-wrapper"><table>
<thead>
<tr>
<th>迭代顺序</th>
<th>方法</th>
</tr>
</thead>
<tbody>
<tr>
<td>从尾到头迭代方法</td>
<td> hasPrevious、previous、previousIndex</td>
</tr>
<tr>
<td> 从头到尾迭代方法</td>
<td> hasNext、next、nextIndex</td>
</tr>
</tbody>
</table>
</div></div><div class="cl-preview-section"><p style="font-size: 20px; line-height: 38px;">LinkedList 实现了 ListIterator 接口，如下图所示：</p>
</div><div class="cl-preview-section"><pre class="  language-java"><code class="prism  language-java"><span class="token comment">// 双向迭代器</span>
<span class="token keyword">private</span> <span class="token keyword">class</span> <span class="token class-name">ListItr</span> <span class="token keyword">implements</span> <span class="token class-name">ListIterator</span><span class="token operator">&lt;</span>E<span class="token operator">&gt;</span> <span class="token punctuation">{</span>
    <span class="token keyword">private</span> Node<span class="token operator">&lt;</span>E<span class="token operator">&gt;</span> lastReturned<span class="token punctuation">;</span><span class="token comment">//上一次执行 next() 或者 previos() 方法时的节点位置</span>
    <span class="token keyword">private</span> Node<span class="token operator">&lt;</span>E<span class="token operator">&gt;</span> next<span class="token punctuation">;</span><span class="token comment">//下一个节点</span>
    <span class="token keyword">private</span> <span class="token keyword">int</span> nextIndex<span class="token punctuation">;</span><span class="token comment">//下一个节点的位置</span>
    <span class="token comment">//expectedModCount：期望版本号；modCount：目前最新版本号</span>
    <span class="token keyword">private</span> <span class="token keyword">int</span> expectedModCount <span class="token operator">=</span> modCount<span class="token punctuation">;</span>
    …………
<span class="token punctuation">}</span>
</code></pre>
</div><div class="cl-preview-section"><p style="font-size: 20px; line-height: 38px;">我们先来看下从头到尾方向的迭代：</p>
</div><div class="cl-preview-section"><pre class="  language-java"><code class="prism  language-java"><span class="token comment">// 判断还有没有下一个元素</span>
<span class="token keyword">public</span> <span class="token keyword">boolean</span> <span class="token function">hasNext</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token keyword">return</span> nextIndex <span class="token operator">&lt;</span> size<span class="token punctuation">;</span><span class="token comment">// 下一个节点的索引小于链表的大小，就有</span>
<span class="token punctuation">}</span>

<span class="token comment">// 取下一个元素</span>
<span class="token keyword">public</span> E <span class="token function">next</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token comment">//检查期望版本号有无发生变化</span>
    <span class="token function">checkForComodification</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token operator">!</span><span class="token function">hasNext</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token comment">//再次检查</span>
        <span class="token keyword">throw</span> <span class="token keyword">new</span> <span class="token class-name">NoSuchElementException</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token comment">// next 是当前节点，在上一次执行 next() 方法时被赋值的。</span>
    <span class="token comment">// 第一次执行时，是在初始化迭代器的时候，next 被赋值的</span>
    lastReturned <span class="token operator">=</span> next<span class="token punctuation">;</span>
    <span class="token comment">// next 是下一个节点了，为下次迭代做准备</span>
    next <span class="token operator">=</span> next<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
    nextIndex<span class="token operator">++</span><span class="token punctuation">;</span>
    <span class="token keyword">return</span> lastReturned<span class="token punctuation">.</span>item<span class="token punctuation">;</span>
<span class="token punctuation">}</span>
</code></pre>
</div><div class="cl-preview-section"><p style="font-size: 20px; line-height: 38px;">上述源码的思路就是直接取当前节点的下一个节点，而从尾到头迭代稍微复杂一点，如下：</p>
</div><div class="cl-preview-section"><pre class="  language-java"><code class="prism  language-java"><span class="token comment">// 如果上次节点索引位置大于 0，就还有节点可以迭代</span>
<span class="token keyword">public</span> <span class="token keyword">boolean</span> <span class="token function">hasPrevious</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token keyword">return</span> nextIndex <span class="token operator">&gt;</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span class="token comment">// 取前一个节点</span>
<span class="token keyword">public</span> E <span class="token function">previous</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token function">checkForComodification</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token operator">!</span><span class="token function">hasPrevious</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span>
        <span class="token keyword">throw</span> <span class="token keyword">new</span> <span class="token class-name">NoSuchElementException</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token comment">// next 为空场景：1:说明是第一次迭代，取尾节点(last);2:上一次操作把尾节点删除掉了</span>
    <span class="token comment">// next 不为空场景：说明已经发生过迭代了，直接取前一个节点即可(next.prev)</span>
    lastReturned <span class="token operator">=</span> next <span class="token operator">=</span> <span class="token punctuation">(</span>next <span class="token operator">==</span> null<span class="token punctuation">)</span> <span class="token operator">?</span> last <span class="token operator">:</span> next<span class="token punctuation">.</span>prev<span class="token punctuation">;</span>
    <span class="token comment">// 索引位置变化</span>
    nextIndex<span class="token operator">--</span><span class="token punctuation">;</span>
    <span class="token keyword">return</span> lastReturned<span class="token punctuation">.</span>item<span class="token punctuation">;</span>
<span class="token punctuation">}</span>
</code></pre>
</div><div class="cl-preview-section"><p style="font-size: 20px; line-height: 38px;">这里复杂点体现在需要判断 next 不为空和为空的场景，代码注释中有详细的描述。</p>
</div><div class="cl-preview-section"><p style="font-size: 20px; line-height: 38px;"><strong>迭代器删除</strong></p>
</div><div class="cl-preview-section"><p style="font-size: 20px; line-height: 38px;">LinkedList 在删除元素时，也推荐通过迭代器进行删除，删除过程如下：</p>
</div><div class="cl-preview-section"><pre class="  language-java"><code class="prism  language-java"><span class="token keyword">public</span> <span class="token keyword">void</span> <span class="token function">remove</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token function">checkForComodification</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token comment">// lastReturned 是本次迭代需要删除的值，分以下空和非空两种情况：</span>
    <span class="token comment">// lastReturned 为空，说明调用者没有主动执行过 next() 或者 previos()，直接报错</span>
    <span class="token comment">// lastReturned 不为空，是在上次执行 next() 或者 previos()方法时赋的值</span>
    <span class="token keyword">if</span> <span class="token punctuation">(</span>lastReturned <span class="token operator">==</span> null<span class="token punctuation">)</span>
        <span class="token keyword">throw</span> <span class="token keyword">new</span> <span class="token class-name">IllegalStateException</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    Node<span class="token operator">&lt;</span>E<span class="token operator">&gt;</span> lastNext <span class="token operator">=</span> lastReturned<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
    <span class="token comment">//删除当前节点</span>
    <span class="token function">unlink</span><span class="token punctuation">(</span>lastReturned<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token comment">// next == lastReturned 的场景分析：从尾到头递归顺序，并且是第一次迭代，并且要删除最后一个元素的情况下</span>
    <span class="token comment">// 这种情况下，previous() 方法里面设置了 lastReturned = next = last,所以 next 和 lastReturned会相等</span>
    <span class="token keyword">if</span> <span class="token punctuation">(</span>next <span class="token operator">==</span> lastReturned<span class="token punctuation">)</span>
        <span class="token comment">// 这时候 lastReturned 是尾节点，lastNext 是 null，所以 next 也是 null，这样在 previous() 执行时，发现 next 是 null，就会把尾节点赋值给 next</span>
        next <span class="token operator">=</span> lastNext<span class="token punctuation">;</span>
    <span class="token keyword">else</span>
        nextIndex<span class="token operator">--</span><span class="token punctuation">;</span>
    lastReturned <span class="token operator">=</span> null<span class="token punctuation">;</span>
    expectedModCount<span class="token operator">++</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
</code></pre>
</div><div class="cl-preview-section"><h2 id="总结" style="font-size: 30px;">总结</h2>
</div><div class="cl-preview-section"><p style="font-size: 20px; line-height: 38px;">LinkedList 适用于要求有顺序、并且会按照顺序进行迭代的场景，主要是依赖于底层的链表结构，在面试中的频率还是蛮高的，相信理清楚上面的源码后，应对面试应该没有问题。</p>
</div>}
                        </div>
                    </div>
                                            <!-- 买过的阅读 -->
                        <div class="art-next-prev clearfix">
                                                                                                <!-- 已买且开放 或者可以试读 -->
                                    <a href="/read/47/article/847">
                                                                    <div class="prev l clearfix">
                                        <div class="icon l">
                                            <i class="imv2-arrow3_l"></i>
                                        </div>
                                        <p>
                                            05 ArrayList 源码解析和设计思路   
                                        </p>
                                    </div>
                                </a>
                                                                                                                            <!-- 已买且开放 或者可以试读 -->
                                    <a href="/read/47/article/849">
                                                                    <div class="next r clearfix">
                                        <p>
                                            07 List 源码会问哪些面试题 
                                        </p>
                                        <div class="icon r">
                                            <i class="imv2-arrow3_r"></i>
                                        </div>

                                    </div>
                                </a>
                                                    </div>
                                    </div>
                <div class="comments-con js-comments-con" id="coments_con">
                </div>

                
            </div>
            
            
            

        </div>
    </div>
</div>

<div class="modal modal-jiaQun-new hide" id="modal-jiaQun">
    <div class="inner" style="">
        <div class="modal-close js-close-jiaQun">
            <i class="imv2-close"></i>
        </div>
        <div class="content">
            <img src="https://img.mukewang.com/5d634d40000119e505400602.jpg">
            <div class="right-info">
                <div class="title">
                    扫码加入慕课Java核心用户群
                </div>
                <div class="desc">
                                            <p class="mb6">验证信息：<span id="joincode">1909271435058473</span><span class="copy js-copy-joincode">复制</span></p>
                                        <p class="mb6">QQ讨论群号：906691736</p>
                                            <p>QQ群URL：<a href="https://jq.qq.com/?_wv=1027&amp;k=55RtSbJ" target="_blank">点击访问</a></p>
                                    </div>
            </div>
            <p class="tip">若遇到搜索不到QQ群或加群失败，请联系客服邮箱:kf@imooc.com</p>
        </div>
    </div>
</div>
 
<!-- 专栏介绍页专栏评价 -->

<!-- 专栏介绍页底部三条评价 -->

<!-- 专栏阅读页弹层目录和介绍页页面目录 -->

<!-- 专栏阅读页发布回复 -->

<!-- 专栏阅读页发布评论 -->

<!-- 专栏阅读页底部评论 -->

<!-- 专栏阅读 单个 评论 -->

<!-- 新增回复和展开三条以外回复 -->

<!-- 立即订阅的弹窗 -->












</div></body></html>